<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">

<html xmlns="http://www.w3.org/1999/xhtml">
 <meta>
  <!-- Stylesheets -->
  <link href="../web.css" type="text/css" rel="stylesheet"></link>
  <link href="../pygmentize.css" type="text/css" rel="stylesheet"></link>
  <title>VLFeat - Documentation - C API</title>
  <link rel="stylesheet" type="text/css" href="../doxygen.css"></style>

  <!-- Scripts-->
  
 </meta>

 <!-- Body Start -->
 <body>
  <div id="header">
   <!-- Google CSE Search Box Begins -->
   <form action="http://www.vlfeat.org/search.html" method="get" id="cse-search-box" enctype="application/x-www-form-urlencoded">
    <div>
     <input type="hidden" name="cx" value="003215582122030917471:oq23albfeam"></input>
     <input type="hidden" name="cof" value="FORID:11"></input>
     <input type="hidden" name="ie" value="UTF-8"></input>
     <input type="text" name="q" size="31"></input>
     <input type="submit" name="sa" value="Search"></input>
    </div>
   </form>
   <script src="http://www.google.com/coop/cse/brand?form=cse-search-box&amp;lang=en" xml:space="preserve" type="text/javascript"></script>
   <!-- Google CSE Search Box Ends -->
   <h1><a shape="rect" href="../index.html" class="plain"><span id="vlfeat">VLFeat</span><span id="dotorg">.org</span></a></h1>
  </div>
  <div id="headbanner">
   Documentation - C API
  </div>
  <div id="pagebody">
   <div id="sidebar"> <!-- Navigation Start -->
    <ul>
<li><a href="../index.html">Home</a>
</li>
<li><a href="../download.html">Download</a>
</li>
<li><a href="../doc.html">Documentation</a>
<ul>
<li><a href="../mdoc/mdoc.html">Matlab API</a>
</li>
<li><a href="index.html" class='active' >C API</a>
</li>
<li><a href="../man/man.html">Man pages</a>
</li>
</ul></li>
<li><a href="../overview/tut.html">Tutorials</a>
</li>
<li><a href="../applications/apps.html">Applications</a>
</li>
</ul>

   </div> <!-- sidebar -->
   <div id="content">
    
    <link rel="stylesheet" type="text/css" href="../doxygen.css"></style>
    <div class="doxygen">
<div>
<!-- Generated by Doxygen 1.7.5.1 -->
  <div id="navrow1" class="tabs">
    <ul class="tablist">
      <li><a href="index.html"><span>Main&#160;Page</span></a></li>
      <li class="current"><a href="pages.html"><span>Related&#160;Pages</span></a></li>
      <li><a href="annotated.html"><span>Data&#160;Structures</span></a></li>
      <li><a href="files.html"><span>Files</span></a></li>
    </ul>
  </div>
</div>
<div class="header">
  <div class="headertitle">
<div class="title">Simple Linear Iterative Clustering (SLIC) </div>  </div>
</div>
<div class="contents">
<div class="textblock"><dl class="author"><dt><b>Author:</b></dt><dd>Andrea Vedaldi</dd></dl>
<p><a class="el" href="slic_8h.html">slic.h</a> implements the SLIC superpixels, an image segmentation algorithm described by <a class="el" href="citelist.html#CITEREF_achanta10slic">[1]</a> .</p>
<ul>
<li><a class="el" href="slic.html#slic-overview">Overview</a></li>
<li><a class="el" href="slic.html#slic-usage">Usage from the C library</a></li>
<li><a class="el" href="slic.html#slic-tech">Technical details</a></li>
</ul>
<h2><a class="anchor" id="slic-overview"></a>
Overview</h2>
<p>SLIC <a class="el" href="citelist.html#CITEREF_achanta10slic">[1]</a> is a simple and efficient method to decompose an image in visually homogeneous regions. It is based on a spatially localized version of k-means clustering. Similar to mean shift or quick shift (<a class="el" href="quickshift_8h.html">quickshift.h</a>), each pixel is associated to a feature vector</p>
<p class="formulaDsp">
<img class="formulaDsp" alt="\[ \Psi(x,y) = \left[ \begin{array}{c} \lambda x \\ \lambda y \\ I(x,y) \end{array} \right] \]" src="form_354.png"/>
</p>
<p>and then k-means clustering is run on those. As discussed below, the coefficient <img class="formulaInl" alt="$ \lambda $" src="form_286.png"/> balances the spatial and appearance components of the feature vectors, imposing a degree of spatial regularization to the extracted regions.</p>
<p>SLIC takes two parameters: the nominal size of the regions (superpixels) <code>regionSize</code> and the strength of the spatial regularization <code>regularizer</code>. The image is first divided into a grid with step <code>regionSize</code>. The center of each grid tile is then used to initialize a corresponding k-means (up to a small shift to avoid image edges). Finally, the k-means centers and clusters are refined by using the Lloyd algorithm, yielding segmenting the image. As a further restriction and simplification, during the k-means iterations each pixel can be assigned to only the <em>22</em> centers corresponding to grid tiles adjacent to the pixel.</p>
<p>The parameter <code>regularizer</code> sets the trade-off between clustering appearance and spatial regularization. This is obtained by setting</p>
<p class="formulaDsp">
<img class="formulaDsp" alt="\[ \lambda = \frac{\mathtt{regularizer}}{\mathtt{regionSize}} \]" src="form_355.png"/>
</p>
<p>in the definition of the feature <img class="formulaInl" alt="$ \psi(x,y) $" src="form_356.png"/>.</p>
<p>After the k-means step, SLIC optionally removes any segment whose area is smaller than a threshld <code>minRegionSize</code> by merging them into larger ones.</p>
<h2><a class="anchor" id="slic-usage"></a>
Usage from the C library</h2>
<p>To compute the SLIC superpixels of an image use the function <a class="el" href="slic_8h.html#adb6a4c91f40fc32528ba88cffba756ab" title="SLIC superpixel segmentation.">vl_slic_segment</a>.</p>
<h2><a class="anchor" id="slic-tech"></a>
Technical details</h2>
<p>SLIC starts by dividing the image domain into a regular grid with <img class="formulaInl" alt="$ M \times N $" src="form_357.png"/> tiles, where</p>
<p class="formulaDsp">
<img class="formulaDsp" alt="\[ M = \lceil \frac{\mathtt{imageWidth}}{\mathtt{regionSize}} \rceil, \quad N = \lceil \frac{\mathtt{imageHeight}}{\mathtt{regionSize}} \rceil. \]" src="form_358.png"/>
</p>
<p>A region (superpixel or k-means cluster) is initialized from each grid center</p>
<p class="formulaDsp">
<img class="formulaDsp" alt="\[ x_i = \operatorname{round} i \frac{\mathtt{imageWidth}}{\mathtt{regionSize}} \quad y_j = \operatorname{round} j \frac{\mathtt{imageWidth}}{\mathtt{regionSize}}. \]" src="form_359.png"/>
</p>
<p>In order to avoid placing these centers on top of image discontinuities, the centers are then moved in a 33 neighbourohood to minimize the edge strength</p>
<p class="formulaDsp">
<img class="formulaDsp" alt="\[ \operatorname{edge}(x,y) = \| I(x+1,y) - I(x-1,y) \|_2^2 + \| I(x,y+1) - I(x,y-1) \|_2^2. \]" src="form_360.png"/>
</p>
<p>Then the regions are obtained by running k-means clustering, started from the centers</p>
<p class="formulaDsp">
<img class="formulaDsp" alt="\[ C = \{ \Psi(x_i,y_j), i=0,1,\dots,M-1\ j=0,1,\dots,N-1 \} \]" src="form_361.png"/>
</p>
<p>thus obtained. K-means uses the standard LLoyd algorithm alternating assigning pixels to the clostest centers a re-estiamting the centers as the average of the corresponding feature vectors of the pixel assigned to them. The only difference compared to standard k-means is that each pixel can be assigned only to the center originated from the neighbour tiles. This guarantees that there are exactly four pixel-to-center comparisons at each round of minimization, which threfore cost <img class="formulaInl" alt="$ O(n) $" src="form_362.png"/>, where <img class="formulaInl" alt="$ n $" src="form_68.png"/> is the number of superpixels.</p>
<p>After k-means has converged, SLIC eliminates any connected region whose area is less than <code>minRegionSize</code> pixels. This is done by greedily merging regions to neighbour ones: the pixels <img class="formulaInl" alt="$ p $" src="form_363.png"/> are scanned in lexicographical order and the corresponding connected components are visited. If a region has already been visited, it is skipped; if not, its area is computed and if this is less than <code>minRegionSize</code> its label is changed to the one of a neighbour region at <img class="formulaInl" alt="$ p $" src="form_363.png"/> that has already been vistied (there is always one except for the very first pixel). </p>
</div></div>
     <!-- Doc Here -->
    </div>
   
   </div>
   <div class="clear">&nbsp;</div>
  </div> <!-- pagebody -->
  <div id="footer">
   &copy; 2007-12 Andrea Vedaldi and Brian Fulkerson
  </div> <!-- footer -->

  <!-- Google Analytics Begins -->
  <script xml:space="preserve" type="text/javascript">
   //<![CDATA[
    var localre = /vlfeat.org/;
    if(document.location.host.search(localre) != -1)
    {
   var gaJsHost = (("https:" == document.location.protocol) ? "https://ssl." : "http://www.");
   document.write(unescape("%3Cscript src='" + gaJsHost + "google-analytics.com/ga.js' type='text/javascript'%3E%3C/script%3E"));
   }
   //]]>
  </script>
  <script xml:space="preserve" type="text/javascript">
    //<![CDATA[
    var localre = /vlfeat.org/;
    if(document.location.host.search(localre) != -1)
    {

   try {
   var pageTracker = _gat._getTracker("UA-4936091-2");
   pageTracker._trackPageview();
   } catch(err) {}

   }
   //]]>
  </script>
  <!-- Google Analytics Ends -->
 </body>
</html>

 
